package newcoder_exp.justPractise;
import java.util.*;
//图的最小生成树算法
public class Pra5 {
    //1. 定义图的数据结构
    public class Graph {
        //点集合，key:顶点编号， val: 顶点
        public Map<Integer, Node> nodes;
        //边集合
        public Set<Edge> edges;

        public class Node {
            //出度顶点集合
            public List<Node> nexts;
            //出度边集合
            public List<Edge> edges;
            public int in; //入度
            public int out; //出度
            public int val; //节点实际存放的值

            public Node(int val) {
                this.nexts = new ArrayList<>();
                this.edges = new ArrayList<>();
                this.in = 0;
                this.out = 0;
                this.val = val;
            }
        }

        public class Edge {
            //入度、出度顶点
            Node in, out;
            //权值
            int weight;
            public Edge(int weight, Node in, Node out) {
                this.in = in;
                this.out = out;
            }
        }
    }


    public class UnionFindSet {
        Map<Graph.Node, Graph.Node> parent = new HashMap<>();
        Map<Graph.Node, Integer> weight = new HashMap<>();
        //并查集
        public UnionFindSet(Collection<Graph.Node> nodes) {
            for (Graph.Node node : nodes) {
                parent.put(node, node); //初始化时，每个节点作为一个集合
                weight.put(node, 1);
            }
        }

        public Graph.Node find(Graph.Node node) {
            Graph.Node p;
            if ((p = parent.get(node)) == node) {
                //根节点
                return node;
            }
            Graph.Node r = find(p);
            parent.put(node, r); //路径压缩
            return r;
        }

        public boolean isConnect(Graph.Node n1, Graph.Node n2) {
            //判断两个节点是否属于同一个集合
            return find(n1) == find(n2);
        }

        public void union(Graph.Node n1, Graph.Node n2) {
            //合并n1,n2所在的集合
            Graph.Node r1 = find(n1), r2 = find(n2);
            if (r1 == r2) return;//已经处于一个集合
            //根据节点数量决定并入哪个集合
            if (weight.get(r1) >= weight.get(r2)) {
                parent.put(r2, r1);
                weight.put(r1, weight.get(r1) + weight.get(r2));
            } else {
                parent.put(r1, r2);
                weight.put(r2, weight.get(r1) + weight.get(r2));
            }
        }
    }

        //2. Kruscal算法
    /* 
        1. 将graph的edges全部加入一个优先级队列，排序规则为权值；
        2. 取出权值最短边，检查边的in和out是否全部加入当前最小生成树的集合;
            若未加入，合并两个集合；
            若已经加入，忽略    
        3. 所有edge遍历完毕；
    */
    public List<Graph.Edge> kruscal(Graph graph) {
        List<Graph.Edge> res = new ArrayList<>();
        Queue<Graph.Edge> queue = new PriorityQueue<>((e1, e2) -> e1.weight - e2.weight);
        UnionFindSet ufs = new UnionFindSet(graph.nodes.values());
        queue.addAll(graph.edges);
        while (!queue.isEmpty()) {
            Graph.Edge cur = queue.poll();
            Graph.Node in = cur.in,
             out = cur.out;
            if (!ufs.isConnect(in, out)) {
                //两个节点不连通，可以添加到最小生成树
                res.add(cur);
                ufs.union(in, out);//合并两个独立的集合
            }
        }
        return res; //将此List<Graph.Edge>替代Graph的edges,就是一个最小生成树
    }

    /* 
        3. Prim算法：
            1. 随机选择一个节点作为起始点，得到他的邻接边,
            使用一个set记录当前已经加入到最小生成树的顶点集中；
            2. 遍历邻接边的所有顶点，若不在set中，加入到一个queue中，作为下一轮遍历（BFS）,
            并将这个邻接边加入到结果边集
                若以加入，忽略
    */
    public List<Graph.Edge> prim(Graph graph) {
        List<Graph.Edge> res = new ArrayList<>();
        Set<Graph.Node> set = new HashSet<>();
        Queue<Graph.Node> queue = new LinkedList<>();
        // for (Graph.Node node: graph.nodes.values()) {
        queue.offer(graph.nodes.get(0));//作为一个起始节点
        while (!queue.isEmpty()) {
            Graph.Node node = queue.poll();
            List<Graph.Edge> edges = node.edges;
            for (Graph.Edge edge: edges) {
                Graph.Node out = edge.out;
                if (!set.contains(out)) {
                    set.add(out);
                    res.add(edge);
                    queue.offer(out);
                }
            }
        }
        return res;
    }
}
